Shareware Grab Bag/Shareware Grab Bag.iso/007/icondoc.arc/OVERVIEW.DOC

Text File | 1985-09-30 | 23.7 KB | 925 lines

              An Overview of Version 5 of the Icon
                      Programming Language




1.  Introduction

   Icon is a high-level programming language with extensive
facilities for processing strings and lists. Icon has several
novel features, including expressions that may produce sequences
of results, goal-directed evaluation that automatically searches
for a successful result, and string scanning that allows opera-
tions on strings to be formulated at a high conceptual level.

   Icon resembles SNOBOL4 [1] in its emphasis on high-level
string processing and a design philosophy that allows ease of
programming and short, concise programs. Like SNOBOL4, storage
allocation and garbage collection are automatic in Icon, and
there are few restrictions on the sizes of objects. Strings,
lists, and other structures are created during program execution
and their size does not need to be known when a program is writ-
ten.  Values are converted to expected types automatically; for
example, numeral strings read in as input can be used in numeri-
cal computations without explicit conversion.  Whereas SNOBOL4
has a pattern-matching facility that is separate from the rest of
the language, string scanning is integrated with the rest of the
language facilities in Icon.  Unlike SNOBOL4, Icon has an
expression-based syntax with reserved words; in appearance, Icon
programs resemble those of several other conventional programming
languages.

   Examples of the kinds of problems for which Icon is well
suited are:

     +  text analysis, editing, and formatting

     +  document preparation

     +  symbolic mathematics

     +  text generation

     +  parsing and translation

     +  data laundry

     +  graph manipulation

   Version 5 of Icon is implemented in C [2]. There are UNIX*
implementations for the AT&T 3B20, PDP-11, Ridge 32, Sun

*UNIX is a trademark of AT&T Bell Laboratories.




                              - 1 -








Workstation, and VAX-11.  There also is a VMS implementation for
the VAX-11 and an MS-DOS implementation for personal computers.
Other implementations are in progress.

   An earlier version of Icon [3] is available on several large-
scale computers, including the CRAY-1, DEC-10, IBM 360/370, PRIME
450/550/650, and CDC Cyber/6000.

   A brief description of some of the representative features of
Icon is given in the following sections. This description is not
rigorous and does not include many features of Icon. See [4] for
a complete description of Version 5 and [5] for a description of
recent additions to the language.


2.  Strings

   Strings of characters may be arbitrarily long, limited only by
the architecture of the computer on which Icon is implemented. A
string may be specified literally by enclosing it in double quo-
tation marks, as in

        greeting := "Hello world"

which assigns an 11-character string to greeting, and

        address := ""

which assigns the zero-length empty string to address.  The
number of characters in a string s, its size, is given by *s. For
example, *greeting is 11 and *address is 0.

   Icon uses the ASCII character set, extended to 256 characters.
There are escape conventions, similar to those of C, for
representing characters that cannot be keyboarded.

   Strings also can be read in and written out, as in

        line := read()

and

        write(line)

Strings can be constructed by concatenation, as in

        element := "(" || read() || ")"

If the concatenation of a number of strings is to be written out,
the write function can be used with several arguments to avoid
actual concatenation:

        write("(",read(),")")




                              - 2 -








   Substrings can be formed by subscripting strings with range
specifications that indicate, by position, the desired range of
characters. For example,

        middle := line[10:20]

assigns to middle the string of characters of line between posi-
tions 10 and 20.  Similarly,

        write(line[2])

writes the second character of line.  The value 0 is used to
refer to the position after the last character of a string. Thus

        write(line[2:0])

writes the substring of line from the second character to the
end, thus omitting the first character.

   An assignment can be made to the substring of string-valued
variable to change its value. For example,

        line[2] := "..."

replaces the second character of line by three dots. Note that
the size of line changes automatically.

   There are many functions for analyzing strings. An example is

        find(s1,s2)

which produces the position in s2 at which s1 occurs as a sub-
string. For example, if the value of greeting is as given ear-
lier,

        find("or",greeting)

produces the value 8.  See Section 4.2 for the handling of situa-
tions in which s1 does not occur in s2, or in which it occurs at
several different positions.


3.  Character Sets

   While strings are sequences of characters, csets are sets of
characters in which membership rather than order is significant.
Csets are represented literally using single enclosing quotation
marks, as in

        vowels := 'aeiouAEIOU'

Two useful built-in csets are &lcase and &ucase, which consist of
the lowercase and uppercase letters, respectively.  Set opera-
tions are provided for csets. For example,



                              - 3 -








        letters := &lcase ++ &ucase

forms the cset union of the lowercase and uppercase letters and
assigns the resulting cset to letters, while

        consonants := letters -- 'aeiouAEIOU'

forms the cset difference of the letters and the vowels and
assigns the resulting cset to consonants.

   Csets are useful in situations in which any one of a number of
characters is significant. An example is the string analysis
function

        upto(c,s)

which produces the position s at which any character in c occurs.
For example,

        upto(vowels,greeting)

produces 2. Another string analysis function that uses csets is

        many(c,s)

which produces the position in s after an initial substring con-
sisting only of characters that occur in s.  An example of the
use of many is in locating words. Suppose, for example, that a
word is defined to consist of a string of letters.  The expres-
sion

        write(line[1:many(letters,line)])

writes a word at the beginning of line. Note the use of the posi-
tion returned by a string analysis function to specify the end of
a substring.


4.  Expression Evaluation

4.1  Conditional Expressions

   In Icon there are conditional expressions that may succeed and
produce a result, or may fail and not produce any result. An
example is the comparison operation

        i > j

which succeeds (and produces the value of j) provided that the
value of i is greater than the value of j, but fails otherwise.

   The success or failure of conditional operations is used
instead of Boolean values to drive control structures in Icon. An
example is



                              - 4 -








        if i > j then k := i else k := j

which assigns the value of i to k if the value of i is greater
than the value of j, but assigns the value of j to k otherwise.

   The usefulness of the concepts of success and failure is
illustrated by find(s1,s2), which fails if s1 does not occur as a
substring of s2.  Thus

        if i := find("or",line) then write(i)

writes the position at which or occurs in line, if it occurs, but
does not write a value if it does not occur.

   Many expressions in Icon are conditional. An example is
read(), which produces the next line from the input file, but
fails when the end of the file is reached. The following expres-
sion is typical of programming in Icon and illustrates the
integration of conditional expressions and conventional control
structures:

        while line := read() do
           write(line)

This expression copies the input file to the output file.

   If an argument of a function fails, the function is not
called, and the function call fails as well. This "inheritance"
of failure allows the concise formulation of many programming
tasks. Omitting the optional do clause in while-do, the previous
expression can be rewritten as

        while write(read())


4.2  Generators

   In some situations, an expression may be capable of producing
more than one result. Consider

        sentence := "Store it in the neighboring harbor"
        find("or",sentence)

Here or occurs in sentence at positions 3, 23, and 33. Most pro-
gramming languages treat this situation by selecting one of the
positions, such as the first, as the result of the expression. In
Icon, such an expression is a generator and is capable of produc-
ing all three positions.

   The results that a generator produces depend on context. In a
situation where only one result is needed, the first is produced,
as in





                              - 5 -








        i := find("or",sentence)

which assigns the value 3 to i.

   If the result produced by a generator does not lead to the
success of an enclosing expression, however, the generator is
resumed to produce another value. An example is

        if (i := find("or",sentence)) > 5 then write(i)

Here the first result produced by the generator, 3, is assigned
to i, but this value is not greater than 5 and the comparison
operation fails. At this point, the generator is resumed and pro-
duces the second position, 23, which is greater than 5. The com-
parison operation then succeeds and the value 23 is written.
Because of the inheritance of failure and the fact that com-
parison operations return the value of their right argument, this
expression can be written in the following more compact form:

        write(5 < find("or",sentence))


   Goal-directed evaluation is inherent in the expression evalua-
tion mechanism of Icon and can be used in arbitrarily complicated
situations.  For example,

        find("or",sentence1) = find("and",sentence2)

succeeds if or occurs in sentence1 at the same position as and
occurs in sentence2.

   A generator can be resumed repeatedly to produce all its
results by using the every-do control structure. An example is

        every i := find("or",sentence)
           do write(i)

which writes all the positions at which or occurs in sentence.
For the example above, these are 3, 23, and 33.

   Generation is inherited like failure, and this expression can
be written more concisely by omitting the optional do clause:

        every write(find("or",sentence))


   There are several built-in generators in Icon. One of the most
frequently used of these is

        i to j

which generates the integers from i to j. This generator can be
combined with every-do to formulate the traditional for-style
control structure:



                              - 6 -








        every k := i to j do
           f(k)

Note that this expression can be written more compactly as

        every f(i to j)


   There are a number of other control structures related to gen-
eration.  One is alternation,

        expr1 | expr2

which generates the results of expr1 followed by the results of
expr2.  Thus

        every write(find("or",sentence1) | find("or",sentence2))

writes the positions of or in sentence1 followed by the positions
of or in sentence2. Again, this sentence can be written more com-
pactly by using alternation in the second argument of find:

        every write(find("or",sentence1 | sentence2))


   Another use of alternation is illustrated by

        (i | j | k) = (0 | 1)

which succeeds if any of i, j, or k has the value 0 or 1.


5.  String Scanning

   The string analysis and synthesis operations described in Sec-
tions 2 and 3 work best for relatively simple operations on
strings.  For complicated operations, the bookkeeping involved in
keeping track of positions in strings becomes burdensome and
error prone.  In such cases, Icon has a string scanning facility
that is analogous in many respects to pattern matching in SNO-
BOL4. In string scanning, positions are managed automatically and
attention is focused on a current position in a string as it is
examined by a sequence of operations.

   The string scanning operation has the form

        s ? expr

where s is the subject string to be examined and expr is an
expression that performs the examination.  A position in the sub-
ject, which starts at 1, is the focus of examination.

   Matching functions change this position.  One matching func-
tion, move(i), moves the position by i and produces the substring



                              - 7 -








of the subject between the previous and new positions. If the
position cannot be moved by the specified amount (because the
subject is not long enough), move(i) fails. A simple example is

        line ? while write(move(2))

which writes successive two-character substrings of line, stop-
ping when there are no more characters.

   Another matching function is tab(i), which sets the position
in the subject to i and also returns the substring of the subject
between the previous and new positions.  For example,

        line ? if tab(10) then write(tab(0))

first sets the position in the subject to 10 and then to the end
of the subject, writing line[10:0].  Note that no value is writ-
ten if the subject is not long enough.

   String analysis functions such as find can be used in string
scanning. In this context, the string that they operate on is not
specified and is taken to be the subject. For example,

        line ? while write(tab(find("or")))
           do move(2)

writes all the substrings of line prior to occurrences of or.
Note that find produces a position, which is then used by tab to
change the position and produce the desired substring. The
move(2) skips the or that is found.

   Another example of the use of string analysis functions in
scanning is

        line ? while tab(upto(letters)) do
           write(tab(many(letters)))

which writes all the words in line.

   As illustrated in the examples above, any expression may occur
in the scanning expression. Unlike SNOBOL4, in which the opera-
tions that are allowed in pattern matching are limited and
idiosyncratic, string scanning is completely integrated with the
rest of the operation repertoire of Icon.


6.  Structures

6.1  Lists

   While strings are sequences of characters, lists in Icon are
sequences of values of arbitrary types. Lists are created by
enclosing the lists of values in brackets. An example is




                              - 8 -








        car1 := ["buick","skylark",1978,2450]

in which the list car1 has four values, two of which are strings
and two of which are integers. Note that the values in a list
need not all be of the same type. In fact, any kind of value can
occur in a list -- even another list, as in

        inventory := [car1,car2,car3,car4]


   Lists also can be created by

        a := list(i,x)

which creates a list of i values, each of which has the value x.

   The values in a list can be referenced by position much like
the characters in a string. Thus

        car1[4] := 2400

changes the last value in car1 to 2400.  A reference that is out
of the range of the list fails. For example,

        write(car1[5])

fails.

   The values in a list a are generated by !a. Thus

        every write(!a)

writes all the values in a.

   Lists can be manipulated like stacks and queues. The function
push(a,x) adds the value of x to the left end of the list a,
automatically increasing the size of a by one. Similarly, pop(a)
removes the leftmost value from a, automatically decreasing the
size of a by one, and produces the removed value.

   A list value in Icon is a pointer (reference) to a structure.
Assignment of a structure in Icon does not copy the structure
itself but only the pointer to it. Thus the result of

        demo := car1

causes demo and car1 to reference the same list. Graphs with
loops can be constructed in this way. For example,

        node1 := ["a"]
        node2 := [node1,"b"]
        push(node1,node2)





                              - 9 -








constructs a structure that can be pictured as follows:


          node1  .->a--.
                 |     |
                 |     |
          node2  '--b<-'



6.2  Tables

   Icon has a table data type similar to that of SNOBOL4. Tables
essentially are sets of pairs of values, an entry value and a
corresponding assigned value. The entry and assigned values may
be of any type, and the assigned value for any entry value can be
looked up automatically.  Thus tables provide a form of associa-
tive access in contrast with the positional access to values in
lists.

   A table is created by an expression such as

        symbols := table(x)

which assigns to symbols a table with the default assigned value
x.  Subsequently, symbols can be referenced by any entry value,
such as

        symbols["there"] := 1

which assigns the value 1 to the thereth entry in symbols.

   Tables grow automatically as new entry values are added.  For
example, the following program segment produces a table contain-
ing a count of the words that appear in the input file:

        words := table(0)
        while line := read() do
           line ? while tab(upto(letters)) do
              words[tab(many(letters))] +:= 1

Here the default assigned value for each word is 0, as given in
table(0), and +:= is an augmented assignment operation that
increments the assigned values by one.  There are augmented
assignment operations for all binary operators.

   Tables can be converted to lists, so that their entry and
assigned values can be accessed by position.  This is done by
sort(t), which produces a list of two-element lists from t, where
each two-element list consists of an entry value and its
corresponding assigned value. For example,






                             - 10 -








        wordlist := sort(words)
        every pair := !wordlist do
           write(pair[1]," : ",pair[2])

writes the words and their counts from words.


7.  Procedures

   An Icon program consists of a sequence of procedure declara-
tions.  An example of a procedure declaration is

        procedure max(i,j)
           if i > j then return i else return j
        end

where the name of the procedure is max and its formal parameters
are i and j. The return expressions return the value of i or j,
whichever is larger.

   Procedures are called like built-in functions. Thus

        k := max(*s1,*s2)

assigns to k the size of the longer of the strings s1 and s2.

   A procedure also may suspend instead of returning. In this
case, a result is produced as in the case of a return, but the
procedure can be resumed to produce other results. An example is
the following procedure that generates the words in the input
file.

        procedure genword()
           local line, letters, words
           letters := &lcase ++ &ucase
           while line := read() do
              line ? while tab(upto(letters)) do {
                 word := tab(many(letters))
                 suspend word
                 }
        end

The braces enclose a compound expression.

   Such a generator is used in the same way that a built-in gen-
erator is used. For example

        every word := genword() do
           if find("or",word) then write(word)

writes only those words that contain the substring or.






                             - 11 -








8.  An Example

   The following program sorts graphs topologically.

        procedure main()
           local sorted, nodes, arcs, roots
           while nodes := read() do {      # get next node list
              arcs := read()               # get arc list
              sorted := ""                 # sorted nodes
                                           # get nodes without predecessors
              while *(roots := nodes -- snodes(arcs)) > 0 do {
                 sorted ||:= roots         # add to sorted nodes
                 nodes --:= roots          # delete these nodes
                 arcs := delarcs(arcs,roots)# delete their arcs
                 }
              if *arcs = 0 then write(sorted)# successfully sorted
              else write("graph has cycle")# cycle if node remains
           }
        end


        procedure snodes(arcs)
           local nodes
           nodes := ""
           arcs ? while move(1) do {       # predecessor
              move(2)                      # skip "->"
              nodes ||:= move(1)           # successor
              move(1)                      # skip ";"
              }
           return nodes
        end


        procedure delarcs(arcs,roots)
           local newarcs, node
           newarcs := ""
           arcs ? while node := move(1) do {# get predecessor node
              if many(roots,node) then move(4)# delete arc from root node
              else newarcs ||:= node || move(4)# else keep arc
              }
           return newarcs
        end

Graph nodes are represented by single characters with a list of
the nodes on one input line followed by a list of arcs. For exam-
ple, the graph











                             - 12 -








                  .---------------.
                  |               |
                  |               |
                  a------>b------>c
                  |       |       |
                  |       |       |
                  |       v       |
                  d------>e-------'


is given as

        abcde
        a->b;a->c;b->c;b->e;d->a;d->e;e->c;

for which the output is

        dabec


   The nodes are represented by csets and automatic type conver-
sion is used to convert strings to csets and vice versa.  Note
the use of augmented assignment operations for concatenation and
in the computation of cset differences.

Acknowledgement

   Icon was designed by the the author in collaboration with Dave
Hanson, Tim Korb, Cary Coutant, and Steve Wampler. The current
implementation is largely the work of Cary Coutant and Steve
Wampler with recent contributions by Bill Mitchell.  Dave Hanson
and Bill Mitchell also made several helpful suggestions on the
presentation of material in this paper.

References


1. Griswold, Ralph E., Poage, James F., and Polonsky, Ivan P.
   The SNOBOL4 Programming Language, second edition.  Prentice-
   Hall, Inc., Englewood Cliffs, New Jersey. 1971.

2. Kernighan, Brian W. and Ritchie, Dennis M. The C Programming
   Language. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
   1978.

3. Griswold, Ralph E. Differences Between Versions 2 and 5 of
   Icon, Technical Report TR 83-5, Department of Computer Sci-
   ence, The University of Arizona. 1983.

4. Griswold, Ralph E. and Griswold, Madge T. The Icon Programming
   Language. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
   1983.





                             - 13 -








5. Griswold, Ralph E. Extensions to Version 5 of the Icon Pro-
   gramming Language, Technical report, Department of Computer
   Science, The University of Arizona. 1985.




   Ralph E. Griswold
   Department of Computer Science
   The University of Arizona

   September 30, 1985













































                             - 14 -